这道题的状态挺难设计的。。。
令 为石子的总数，那么操作次数最多为
如果石子数量全不为一，那么先手必胜的条件为 为奇数，因为他一定可以保证操作 次。
反之后手必胜。
问题在于石子数量可能为 ，这时去掉这颗石子便无法合并。
所以状态应该与石子数量为 的堆数，石子数量不为 的堆的最大操作次数有关。
令 表示剩下 堆数量为 的石子堆，其余石子堆能操作 次的 函数值。
那么后继状态有五种种：
- 在石子数不为 的石子堆取掉一颗石子
- 合并两堆不为 的石子堆
- 取掉一堆为 的石子堆
- 将两堆为 的石子堆合并
- 将一堆为 和一堆不为 的石子堆合并
边界条件就是最开始讲的。
#include <cstdio>
#include <iostream>
using namespace std;
const int MAXN = 50 , MAXV = MAXN * 1000;
int T , n;
int SG[ MAXN + 5 ][ MAXV + 5 ];
int dfs( int Cnt1 , int oper ) {
if( SG[ Cnt1 ][ oper ] ) return SG[ Cnt1 ][ oper ];
if( oper == 1 ) return SG[ Cnt1 ][ oper ] = dfs( Cnt1 + 1 , 0 );
if( Cnt1 == 0 ) return SG[ Cnt1 ][ oper ] = oper % 2;
int Mex = 2;
if( Cnt1 ) Mex = min( Mex , dfs( Cnt1 - 1 , oper ) );
if( oper ) Mex = min( Mex , dfs( Cnt1 , oper - 1 ) );
if( Cnt1 >= 2 ) Mex = min( Mex , dfs( Cnt1 - 2 , oper + 2 + ( oper ? 1 : 0 ) ) );
if( Cnt1 && oper ) Mex = min( Mex , dfs( Cnt1 - 1 , oper + 1 ) );
return SG[ Cnt1 ][ oper ] = Mex == 0 ? 1 : 0;
}
int main( ) {
scanf("%d",&T);
for( int t = 1 ; t <= T ; t ++ ) {
printf("Case #%d: ", t );
int Cnt1 = 0 , oper = 0;
scanf("%d",&n);
for( int i = 1 , x ; i <= n ; i ++ ) {
scanf("%d",&x);
if( x == 1 ) Cnt1 ++;
else oper += x + 1;
}
if( oper ) oper --; //合并次数=堆数-1
puts( dfs( Cnt1 , oper ) ? "Alice" : "Bob" );
}
return 0;
}